package main

import (
	"fmt"
)

/**
执行用时：8 ms, 在所有 Go 提交中击败了60.00%的用户
内存消耗：3.9 MB, 在所有 Go 提交中击败了88.42%的用户
 */
func isScramble(s1 string, s2 string) bool {

	n := len(s1)
	f := make([][][]bool, n)
	for i := 0; i < n; i++ {
		f[i] = make([][]bool, n)
		for j := 0; j < n; j++ {
			f[i][j] = make([]bool, n + 1)
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			f[i][j][1] = s1[i] == s2[j]
		}
	}

	for lg := 2; lg <= n; lg++ {
		for i := 0; i + lg - 1 < n; i++ {
			for j := 0; j + lg - 1 < n; j++ {
				for k := 1; k < lg; k++ {
					if f[i][j][k] && f[i + k][j + k][lg - k] {
						f[i][j][lg] = true
						break
					}
					if f[i][j + lg - k][k] && f[i + k][j][lg - k] {
						f[i][j][lg] = true
						break
					}
				}
			}
		}
	}

	return f[0][0][n];
}

func main() {

	fmt.Println(isScramble("great", "rgeat"))
}
